//35. 搜索插入位置
// 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
// 请必须使用时间复杂度为 O(log n) 的算法

#include <stdio.h>

int searchInsert(int* nums, int numsSize, int target) 
{
    int left = 0,right = numsSize-1;
   while(left <= right){
       int mid = left + (right - left)/2;
       if(left == right){
           return target > nums[left] ? left+1 : left;
       }
       if(nums[mid] == target)
           return mid;
       else if(nums[mid] > target)
           right = mid;
       else if(nums[mid] < target)
           left = mid + 1;
   }
   return -1;
}

int main()
{
    int s[4] = {1,3,5,6};
    int target = 5;
    printf("%d\n",searchInsert(s,4,target));
    return 0;
}